package org.dslforge.aurum;

import static java.util.Collections.*;
import static org.dslforge.aurum.Symbol.*;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

import org.dslforge.aurum.Automata.Transition;

class ControlDFAConstructor {
	private final static Symbol DUMMY = terminal("$dummy");

	private List<Collection<LR0Item>> LR0Collection;

	private List<Collection<LR1Item>> LR1Collection;

	private Automata<Symbol, Handle> controlDFA;

	private AugmentedGrammar grammar;

	private Map<KernelItem, Set<Symbol>> lookaheads = new HashMap<KernelItem, Set<Symbol>>();

	private Map<KernelItem, Set<KernelItem>> propapagation = new HashMap<KernelItem, Set<KernelItem>>();

	private Stack<KernelItem> toBePropagated = new Stack<KernelItem>();

	ControlDFAConstructor(AugmentedGrammar grammar) {
		this.grammar = grammar;
		initialize();
		discoverLookaheadAndPropagation();
		propagateLookahead();
		constructLR1Collection();
	}

	private void initialize() {
		this.LR0Collection = grammar.itemsCollection();
		this.LR1Collection = new ArrayList<Collection<LR1Item>>(LR0Collection.size());
		this.controlDFA = new Automata<Symbol, Handle>(LR0Collection.size());
		for (int i = 0; i < LR0Collection.size(); i++) {
			LR1Collection.add(new HashSet<LR1Item>());
			for (LR0Item item : LR0Collection.get(i))
				lookaheads.put(new KernelItem(i, item), new HashSet<Symbol>());
		}
	}

	private void discoverLookaheadAndPropagation() {
		for (int i = 0; i < LR0Collection.size(); i++)
			for (LR0Item item : LR0Collection.get(i))
				if (grammar.isKernel(item))
					discoverLookaheadAndPropagation(i, item);
	}

	private void discoverLookaheadAndPropagation(int i, LR0Item kernel) {
		Collection<LR0Item> items = LR0Collection.get(i);
		for (LR1Item LR1 : grammar.closureForLR1Items(singleton(new LR1Item(kernel, DUMMY))))
			if (!LR1.item.isHandle()) {
				KernelItem kernelItem = new KernelItem(indexOf(grammar.goToForLR0Items(items,
						LR1.item.expected)), LR1.item.next());
				if (LR1.lookahead.equals(DUMMY)) {
					KernelItem from = new KernelItem(i, kernel);
					Set<KernelItem> to = propapagation.get(from);
					if (to == null) {
						to = new HashSet<KernelItem>();
						propapagation.put(from, to);
					}
					to.add(kernelItem);
				} else {
					lookaheads.get(kernelItem).add(LR1.lookahead);
					if (!toBePropagated.contains(kernelItem))
						toBePropagated.push(kernelItem);
				}
			}
	}

	private void propagateLookahead() {
		KernelItem start = new KernelItem(0, new LR0Item(grammar.startProduction, 0));
		lookaheads.get(start).add(EOF);
		toBePropagated.add(start);
		while (!toBePropagated.isEmpty()) {
			KernelItem from = toBePropagated.pop();
			Set<KernelItem> destinations = propapagation.get(from);
			if (destinations != null)
				for (KernelItem to : destinations)
					if (lookaheads.get(to).addAll(lookaheads.get(from)))
						toBePropagated.add(to);
		}
	}

	private void constructLR1Collection() {
		for (KernelItem kernelItem : lookaheads.keySet())
			for (Symbol lookahead : lookaheads.get(kernelItem))
				LR1Collection.get(kernelItem.index).add(new LR1Item(kernelItem.item, lookahead));
		for (Collection<LR1Item> item : LR1Collection)
			item.addAll(grammar.closureForLR1Items(item));
	}

	final Automata<Symbol, Handle> build() {
		for (int i = 0; i < controlDFA.stateCount(); i++) {
			for (Symbol symbol : symbols(i))
				controlDFA.connect(i, symbol, goTo(i, symbol));
			setHandleAndLookahead(i);
		}
		checkShiftReduceConflict();
		return controlDFA;
	}

	private Set<Symbol> symbols(int index) {
		Set<Symbol> symbols = new HashSet<Symbol>();
		for (LR1Item LR1 : LR1Collection.get(index))
			if (!LR1.item.isHandle())
				symbols.add(LR1.item.expected);
		return symbols;
	}

	private int goTo(int index, Symbol x) {
		Collection<LR1Item> items = grammar.goToForLR1Items(LR1Collection.get(index), x);
		for (int i = 0; i < LR1Collection.size(); i++)
			if (LR1Collection.get(i).containsAll(items))
				return i;
		return -1;
	}

	private void setHandleAndLookahead(int state) {
		Handle handle = null;
		for (LR1Item LR1 : LR1Collection.get(state))
			if (LR1.item.isHandle()) {
				handle = controlDFA.acceptStates.get(state);
				if (handle == null) {
					handle = new Handle(LR1.item.production);
					controlDFA.setAccept(state, handle);
					handle.lookaheads.add(LR1.lookahead);
				} else if (handle.production.equals(LR1.item.production)) {
					handle.lookaheads.add(LR1.lookahead);
				} else
					throw new RuntimeException();
			}
		if (handle != null && handle.production.equals(grammar.startProduction)) {
			handle.accept = true;
			handle.lookaheads.add(Symbol.EOF);
		}
	}

	private int indexOf(Collection<LR0Item> items) {
		return LR0Collection.indexOf(items);
	}

	private void checkShiftReduceConflict() {
		for (int state : controlDFA.acceptStates.keySet()) {
			Handle handle = controlDFA.acceptStates.get(state);
			for (Transition<Symbol> transition : controlDFA.transitionTable.get(state))
				if (handle.lookaheads.contains(transition.symbols))
					throw new RuntimeException();
		}
	}
}

class Handle {
	final Production production;

	final Set<Symbol> lookaheads = new HashSet<Symbol>();

	boolean accept = false;

	Handle(Production production) {
		this.production = production;
	}
}

class LR0Item {
	final int position;

	final Production production;

	final Symbol expected;

	LR0Item(Production production, int position) {
		this.production = production;
		this.position = position;
		this.expected = production.get(position);
	}

	boolean isHandle() {
		return expected == null;
	}

	LR0Item next() {
		return new LR0Item(production, position + 1);
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == this)
			return true;
		if (obj == null || obj.getClass() != getClass())
			return false;
		LR0Item item = (LR0Item) obj;
		return item.production.equals(production) && item.position == position;
	}

	@Override
	public int hashCode() {
		return production.hashCode() * 37 + position;
	}

	@Override
	public String toString() {
		StringBuffer buffer = new StringBuffer();
		buffer.append(production.nonterminal).append(" -> ");
		for (int i = 0; i < production.symbols.length; i++) {
			if (position == i)
				buffer.append(".");
			buffer.append(production.symbols[i]).append(" ");
		}
		if (position == production.symbols.length)
			buffer.append(".");
		return buffer.toString();
	}
}

class KernelItem {
	final int index;

	final LR0Item item;

	KernelItem(int index, LR0Item item) {
		this.index = index;
		this.item = item;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == this)
			return true;
		if (obj == null || obj.getClass() != getClass())
			return false;
		KernelItem item = (KernelItem) obj;
		return item.item.equals(this.item) && item.index == index;
	}

	@Override
	public int hashCode() {
		return item.hashCode() * 37 + index;
	}
}

class LR1Item {
	final LR0Item item;

	final Symbol lookahead;

	public LR1Item(Production production, int position, Symbol lookahead) {
		this.item = new LR0Item(production, position);
		this.lookahead = lookahead;
	}

	public LR1Item(LR0Item item, Symbol lookahead) {
		this.item = item;
		this.lookahead = lookahead;
	}

	@Override
	public boolean equals(Object obj) {
		if (obj == this)
			return true;
		if (obj == null || obj.getClass() != getClass())
			return false;
		LR1Item item = (LR1Item) obj;
		return item.item.equals(this.item) && lookahead.equals(item.lookahead);
	}

	@Override
	public int hashCode() {
		return item.hashCode() * 37 + lookahead.hashCode();
	}

	@Override
	public String toString() {
		return item.toString() + ", " + lookahead;
	}
}
